package org.czl.leetCode1;

import java.util.PriorityQueue;

public class L1631 {
    public static void main(String[] args) {
        //1,2,2],[3,8,2],[5,3,5]
        System.out.println(minimumEffortPath(new int[][]{{1, 2, 2}, {3, 8, 2}, {5, 3, 5}}));
    }

    static int[] xx = new int[]{0, 0, 1, -1};
    static int[] yy = new int[]{1, -1, 0, 0};
    public static int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[2] - b[2]));
        queue.add(new int[]{0,0,0});
        int[][] distance = new int[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                distance[i][j] = Integer.MAX_VALUE;
            }
        }
        distance[0][0] = 0;
        boolean[][] set = new boolean[m][n];
        while(!queue.isEmpty()){
            int[] arr = queue.poll();
            int x = arr[0];
            int y = arr[1];
            int coin = arr[2];
            if(set[x][y]){
                continue;
            }
            set[x][y] = true;
            if(x == m - 1 && y == n - 1){
                return coin;
            }
            for(int i = 0; i < 4; i++){
                int fx = x + xx[i];
                int fy = y + yy[i];
                //放越界
                if(fx >= 0 && fx < m && fy >= 0 && fy < n && !set[fx][fy]){
                    int ret = Math.max(coin, Math.abs(heights[fx][fy] - heights[x][y]));
                    if(ret < distance[fx][fy]){
                        distance[fx][fy] = ret;
                        queue.add(new int[]{fx, fy, ret});
                    }

                }
            }
        }
        return distance[m - 1][n - 1];
    }
}
